/**
 * 279. 完全平方数
 */
public class Solution_279 {
    /**
     * 动态规划
     * <p>
     * 时间复杂度：O(N*sqrt(N))
     * <p>
     * 空间复杂度：O(N)
     */
    public int numSquares(int n) {
        // 默认初始化值都为 0
        int[] dp = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            // 每次都将当前数字先更新为最大的结果，即 dp[i]=i，
            // 比如 i=4，最坏结果为 4=1+1+1+1 即为 4 个数字
            dp[i] = i;
            // 动态转移方程：dp[i] = min(dp[i], dp[i - j * j] + 1)，
            // i 表示当前数字，j*j 表示平方数
            for (int j = 1; i - j * j >= 0; j++) {
                dp[i] = Math.min(dp[i], dp[i - j * j] + 1);
            }
        }
        return dp[n];
    }

    public static void main(String[] args) {
        Solution_279 solution = new Solution_279();
        int ans = solution.numSquares(12);
        System.out.println(ans);
        ans = solution.numSquares(13);
        System.out.println(ans);
    }
}
